package gold.digger;

import gold.vo.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC671 {
    public long startExecuteTime = System.currentTimeMillis();

    class Solution {
        int ans;
        int rootvalue;

        public int findSecondMinimumValue(TreeNode root) {
            ans = -1;
            rootvalue = root.val;
            dfs(root);
            return ans;
        }

        public void dfs(TreeNode node) {
            if (node == null) {
                return;
            }
            if (ans != -1 && node.val >= ans) {
                return;
            }
            if (node.val > rootvalue) {
                ans = node.val;
            }
            dfs(node.left);
            dfs(node.right);
        }
    }

    class Solution_Difficult_thinking {
        public int findSecondMinimumValue(TreeNode root) {
            if (null == root) return -1;
            final int secondMinimumValueRecur = findSecondMinimumValueRecur(root, root.val);
            return secondMinimumValueRecur == root.val ? -1 : secondMinimumValueRecur;
        }

        public int findSecondMinimumValueRecur(TreeNode root, int prevMin) {
            if (null == root) return -1;
            if (null == root.left && root.val <= prevMin) return root.val;
            if (root.val > prevMin) return root.val;
            if (root.left.val == root.right.val) {
                int leftSide = findSecondMinimumValueRecur(root.left, prevMin);
                int rightSide = findSecondMinimumValueRecur(root.right, prevMin);
                return Math.max(leftSide, rightSide);
            }
            if (root.left.val > root.right.val) return findSecondMinimumValueRecur(root.right, prevMin);
            else return findSecondMinimumValueRecur(root.left, prevMin);
        }
    }

    public void run() {
        Solution solution = new Solution();
        TreeNode root = TreeNode.createTree("[1,1,3,1,1,3,4,3,1,1,1,3,8,4,8,3,3,1,6,2,1]");
        System.out.println(solution.findSecondMinimumValue(root));
    }

    public static void main(String[] args) throws Exception {
        LC671 an = new LC671();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
